<template><div><ul>
<li>单链表： 一般常用来表示邻接表，用来存储图和树的</li>
<li>双向链表：用来优化某些问题</li>
</ul>
<h2 id="模板" tabindex="-1"><a class="header-anchor" href="#模板"><span>模板</span></a></h2>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#7F848E;font-style:italic">// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> head, </span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[N], </span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[N], idx;</span></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 初始化</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> init</span><span style="color:#ABB2BF">()</span></span>
<span class="line"><span style="color:#ABB2BF">{</span></span>
<span class="line"><span style="color:#ABB2BF">    head </span><span style="color:#C678DD">=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    idx </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 在链表头插入一个数a</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> insert</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> a</span><span style="color:#ABB2BF">)</span></span>
<span class="line"><span style="color:#ABB2BF">{</span></span>
<span class="line"><span style="color:#E5C07B">    e</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> a, </span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head, head </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> idx </span><span style="color:#C678DD">++</span><span style="color:#ABB2BF"> ;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 将头结点删除，需要保证头结点存在</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> remove</span><span style="color:#ABB2BF">()</span></span>
<span class="line"><span style="color:#ABB2BF">{</span></span>
<span class="line"><span style="color:#ABB2BF">    head </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[head];</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="模拟链表" tabindex="-1"><a class="header-anchor" href="#模拟链表"><span>模拟链表</span></a></h2>
<p><img src="@source/notes/基础算法/2.数据结构/1-1.png" alt=""></p>
<h3 id="输入样例" tabindex="-1"><a class="header-anchor" href="#输入样例"><span>输入样例</span></a></h3>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#D19A66">10</span></span>
<span class="line"><span style="color:#ABB2BF">H </span><span style="color:#D19A66">9</span></span>
<span class="line"><span style="color:#ABB2BF">I </span><span style="color:#D19A66">1</span><span style="color:#D19A66"> 1</span></span>
<span class="line"><span style="color:#ABB2BF">D </span><span style="color:#D19A66">1</span></span>
<span class="line"><span style="color:#ABB2BF">D </span><span style="color:#D19A66">0</span></span>
<span class="line"><span style="color:#ABB2BF">H </span><span style="color:#D19A66">6</span></span>
<span class="line"><span style="color:#ABB2BF">I </span><span style="color:#D19A66">3</span><span style="color:#D19A66"> 6</span></span>
<span class="line"><span style="color:#ABB2BF">I </span><span style="color:#D19A66">4</span><span style="color:#D19A66"> 5</span></span>
<span class="line"><span style="color:#ABB2BF">I </span><span style="color:#D19A66">4</span><span style="color:#D19A66"> 5</span></span>
<span class="line"><span style="color:#ABB2BF">I </span><span style="color:#D19A66">3</span><span style="color:#D19A66"> 4</span></span>
<span class="line"><span style="color:#ABB2BF">D </span><span style="color:#D19A66">6</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="输出样例" tabindex="-1"><a class="header-anchor" href="#输出样例"><span>输出样例</span></a></h3>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#D19A66">6</span><span style="color:#D19A66"> 4</span><span style="color:#D19A66"> 6</span><span style="color:#D19A66"> 5</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div></div></div><h3 id="示例代码" tabindex="-1"><a class="header-anchor" href="#示例代码"><span>示例代码</span></a></h3>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD">+</span><span style="color:#D19A66">10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> head,</span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[N],</span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[N],idx;</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> init</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#ABB2BF">    head </span><span style="color:#C678DD">=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span><span style="color:#7F848E;font-style:italic"> // 表示指向空集</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> add_to_head</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> x</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">    e</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> x;</span></span>
<span class="line"><span style="color:#E5C07B">    ne</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head;</span></span>
<span class="line"><span style="color:#ABB2BF">    head </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> idx;</span></span>
<span class="line"><span style="color:#ABB2BF">    idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> add</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> k</span><span style="color:#ABB2BF">,</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> x</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">    e</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> x;</span></span>
<span class="line"><span style="color:#E5C07B">    ne</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[k];</span></span>
<span class="line"><span style="color:#E5C07B">    ne</span><span style="color:#ABB2BF">[k] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> idx;</span></span>
<span class="line"><span style="color:#ABB2BF">    idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> del</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> k</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">     ne</span><span style="color:#ABB2BF">[k] </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[</span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[k]];</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#61AFEF">    init</span><span style="color:#ABB2BF">();</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        char</span><span style="color:#ABB2BF"> c;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">c;</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(c </span><span style="color:#C678DD">==</span><span style="color:#98C379"> 'H'</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> x;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x;</span></span>
<span class="line"><span style="color:#61AFEF">            add_to_head</span><span style="color:#ABB2BF">(x);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span><span style="color:#C678DD">else</span><span style="color:#C678DD"> if</span><span style="color:#ABB2BF"> (c </span><span style="color:#C678DD">==</span><span style="color:#98C379"> 'D'</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> k;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">k;</span></span>
<span class="line"><span style="color:#C678DD">            if</span><span style="color:#ABB2BF">(k </span><span style="color:#C678DD">==</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">) head </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[head];</span></span>
<span class="line"><span style="color:#61AFEF">            del</span><span style="color:#ABB2BF">(k</span><span style="color:#C678DD">-</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span><span style="color:#C678DD">else</span><span style="color:#ABB2BF"> {</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> k,x;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">k</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x;</span></span>
<span class="line"><span style="color:#61AFEF">            add</span><span style="color:#ABB2BF">(k</span><span style="color:#C678DD">-</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">,x);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i</span><span style="color:#C678DD">=</span><span style="color:#ABB2BF">head;i</span><span style="color:#C678DD">!=-</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">=</span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[i]) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[i]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">    return</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="练习" tabindex="-1"><a class="header-anchor" href="#练习"><span>练习</span></a></h2>
<blockquote>
<p>练习题：https://www.nowcoder.com/practice/97dc1ac2311046618fd19960041e3c6f</p>
</blockquote>
<p><img src="@source/notes/基础算法/2.数据结构/1-2.png" alt=""></p>
<h3 id="示例代码-1" tabindex="-1"><a class="header-anchor" href="#示例代码-1"><span>示例代码</span></a></h3>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379"> &#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD"> +</span><span style="color:#D19A66"> 10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> head, </span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[N], </span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[N], idx;</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> init</span><span style="color:#ABB2BF">() {</span></span>
<span class="line"><span style="color:#ABB2BF">    head </span><span style="color:#C678DD">=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> insert</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> x</span><span style="color:#ABB2BF">, </span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> y</span><span style="color:#ABB2BF">) {</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> ans </span><span style="color:#C678DD">=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span><span style="color:#C678DD">for</span><span style="color:#ABB2BF"> (</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head; i </span><span style="color:#C678DD">!=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">; i </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[i]) {</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF"> (</span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[i] </span><span style="color:#C678DD">==</span><span style="color:#ABB2BF"> x ) </span><span style="color:#C678DD">break</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">        ans </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> i;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (ans </span><span style="color:#C678DD">==</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">) {</span></span>
<span class="line"><span style="color:#E5C07B">        e</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> y;</span></span>
<span class="line"><span style="color:#E5C07B">        ne</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head;</span></span>
<span class="line"><span style="color:#ABB2BF">        head </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    else</span><span style="color:#ABB2BF">{</span></span>
<span class="line"><span style="color:#E5C07B">        e</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> y;</span></span>
<span class="line"><span style="color:#E5C07B">        ne</span><span style="color:#ABB2BF">[idx] </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[ans];</span></span>
<span class="line"><span style="color:#E5C07B">        ne</span><span style="color:#ABB2BF">[ans] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> del</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> x</span><span style="color:#ABB2BF">) {</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (head </span><span style="color:#C678DD">==</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">) </span><span style="color:#C678DD">return</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> ans </span><span style="color:#C678DD">=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span><span style="color:#C678DD">for</span><span style="color:#ABB2BF"> (</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head; i </span><span style="color:#C678DD">!=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">; i </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[i]) {</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF"> (</span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[i] </span><span style="color:#C678DD">==</span><span style="color:#ABB2BF"> x ) </span><span style="color:#C678DD">break</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">        ans </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> i;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (ans </span><span style="color:#C678DD">==</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF"> ) head </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[head];</span><span style="color:#C678DD">else</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[ans] </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[</span><span style="color:#E5C07B">ne</span><span style="color:#ABB2BF">[ans]];</span></span>
<span class="line"></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">() {</span></span>
<span class="line"><span style="color:#ABB2BF">    ios::</span><span style="color:#61AFEF">sync_with_stdio</span><span style="color:#ABB2BF">(</span><span style="color:#D19A66">false</span><span style="color:#ABB2BF">);</span></span>
<span class="line"><span style="color:#61AFEF">    init</span><span style="color:#ABB2BF">();</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> m;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">m;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF"> (m</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">) {</span></span>
<span class="line"><span style="color:#ABB2BF">        string op;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">op;</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF"> (op </span><span style="color:#C678DD">==</span><span style="color:#98C379"> "insert"</span><span style="color:#ABB2BF">) {</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> x,y;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">y;</span></span>
<span class="line"><span style="color:#61AFEF">            insert</span><span style="color:#ABB2BF">(x,y);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span><span style="color:#C678DD">else</span><span style="color:#ABB2BF"> {</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> x;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">x;</span></span>
<span class="line"><span style="color:#61AFEF">            del</span><span style="color:#ABB2BF">(x);</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (head </span><span style="color:#C678DD">==</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">"NULL"</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">    else</span><span style="color:#C678DD"> for</span><span style="color:#ABB2BF"> (</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> head;i </span><span style="color:#C678DD">!=</span><span style="color:#C678DD"> -</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;i </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> ne</span><span style="color:#ABB2BF">[i]) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">e</span><span style="color:#ABB2BF">[i]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div></div></template>


